The present invention relates to a data search method and apparatus for locating data in a content addressable memory.
A content addressable memory (xe2x80x9cCAMxe2x80x9d) typically stores data in a plurality of memory locations. The CAM may include value matching logic that compares input data against the stored data and generates an indicator signal identifying those memory locations where the input value matches a stored value. A value match often is called a xe2x80x9chit.xe2x80x9d Such properties of CAMs are well-known.
A CAM may be used as part of a prioritized search. That is, if input data causes several hits, there may be only desired match. The desired match may be identified by a prioritization scheme that operates independently of the CAM process. In this case, a search may be performed against the matching entries to identify the one that should be identified as a match. Unfortunately, a prioritized search typically implies an entry-for-entry search of the matching locations, a process that can introduce severe latency into the search process.
By way of example, consider a CAM search that is applied to a circular FIFO queue. The search may attempt to identify an oldest match in the queue. In a straightforward search algorithm, content addressing may identify one or more matching entries. Matches may be recorded as flags in a register. If there are multiple matches, an iterative register shift might be used to identify the oldest matching location. The iterative nature of the shift takes time.
Accordingly, there is a need in the art for a fast prioritized CAM search algorithm. What is desired is a CAM that outputs at most one hit even when there are multiple matching CAM locationsxe2x80x94the hit corresponding to the location that is ranked highest according to the priority scheme.
Embodiments of the present invention provide a prioritized content addressable memory having an at most one hit property despite the presence of redundant values stored therein.